from copy import deepcopy

system_example = {
    'res_available': {'A': 0, 'B': 3, 'C': 2, 'D': 2},
    'progress': [
        {
            'name': 'P0',
            'res_has': {'A': 1, 'B': 0, 'C': 1, 'D': 1},
            'res_need': {'A': 0, 'B': 4, 'C': 3, 'D': 1},
            'is_stop': False
        },
        {
            'name': 'P1',
            'res_has': {'A': 0, 'B': 2, 'C': 2, 'D': 1},
            'res_need': {'A': 0, 'B': 3, 'C': 4, 'D': 2},
            'is_stop': False
        },
        {
            'name': 'P2',
            'res_has': {'A': 0, 'B': 2, 'C': 1, 'D': 2},
            'res_need': {'A': 1, 'B': 0, 'C': 3, 'D': 4},
            'is_stop': False
        },
        {
            'name': 'P3',
            'res_has': {'A': 0, 'B': 3, 'C': 1, 'D': 0},
            'res_need': {'A': 0, 'B': 3, 'C': 2, 'D': 0},
            'is_stop': False
        },
        {
            'name': 'P4',
            'res_has': {'A': 1, 'B': 0, 'C': 2, 'D': 1},
            'res_need': {'A': 0, 'B': 4, 'C': 2, 'D': 3},
            'is_stop': False
        }
    ],
    'select': ''  # P3, for example
}

solution_example = {
    'is_deadlock': False,
    'step': []  # system1, system2 ...
}


# res1 + res2
def resource_add(res1, res2):
    res = {}
    for key in res1.keys():
        res[key] = res1[key] + res2[key]
    return res


# res1 - res2
def resource_minus(res1, res2):
    res = {}
    for key in res1.keys():
        res[key] = res1[key] - res2[key]
    return res


# res1 >= res2
def resource_geq(res1, res2):  # geq means Greater or Equal.
    for key in res1.keys():
        if res1[key] < res2[key]:
            return False
    return True


# 根据系统初态计算是否会发生死锁，并给出解决方案步骤
def bank_algorithm(system):  # -> solution
    solution = {
        'is_deadlock': False,
        'step': []  # system1, system2 ...
    }
    is_change = True  # 较上一次循环有变化，因此继续执行
    is_finish = False  # 所有的进程都执行完成，即没有死锁
    while is_change:
        is_change = False
        is_finish = False
        for progress in system['progress']:
            if not progress['is_stop'] and resource_geq(system['res_available'], progress['res_need']):
                system['select'] = progress['name']
                solution['step'].append(deepcopy(system))
                system['select'] = ''
                system['res_available'] = resource_add(system['res_available'], progress['res_has'])
                progress['res_has'] = resource_minus(progress['res_has'], progress['res_has'])
                progress['res_need'] = resource_minus(progress['res_need'], progress['res_need'])
                progress['is_stop'] = True
                is_change = True
                break
        else:
            solution['step'].append(deepcopy(system))
            is_finish = True
    solution['is_deadlock'] = not is_finish
    return solution


def print_system(system):
    line_left = '{:>6}{:>12}'
    line_right = ''
    for key in system['res_available'].keys():
        line_right += '{' + '{}:>6'.format(key) + '}'
    # 资源编号
    print(line_left.format('', '') + line_right.format(**{key: key for key in system['res_available'].keys()}))
    # 可用资源
    print(line_left.format('', 'Available') + line_right.format(**system['res_available']))
    for progress in system['progress']:
        print(line_left.format(('> ' if system['select'] == progress['name'] else '') + progress['name'], 'Has')
              + line_right.format(**progress['res_has']))
        print(line_left.format('', 'Need') + line_right.format(**progress['res_need']))
    print('-' * 40)


# Unit test
if __name__ == '__main__':
    solu = bank_algorithm(system_example)
    print(solu['is_deadlock'])
    for sys in solu['step']:
        print_system(sys)
